This invention relates in general to databases and in particular to maintaining tables of databases in sorted order.
Relational databases store information as tables or relations. For example, in a database schema describing an organization, one relation may store information describing employees and another relation may store information describing departments. Each row of the department relation may represent a department and each row of the employee relation may represent an employee. Databases provide query language interfaces for users to access data stored in databases. An example query language interface typically supported by databases is the structured query language (SQL). The query languages allow users to perform various operations to extract desired set of results from tables stored in database. For example, a user can join two tables, return a subset of columns of one or more tables, perform aggregate operations, and so on.
Processing database queries often requires sorting of a data. Databases perform sort operation on tables as well as intermediate results while processing queries. The efficiency of the sort operation affects performance of several queries. If a database performs sorting inefficiently, queries using sorted data also perform inefficiently. Some databases store table data in sorted form on persistent storage so that the data is ready for use while processing queries. However, databases often perform modify data stored in tables, thereby changing the values stored in the tables. As a result, a sorted table over time becomes unsorted. If the stored data becomes unsorted, the database needs to perform sort the data while processing queries resulting in inefficient processing of queries.